<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 最长公共子序列 -->
    <script>
      var longestCommonSubsequence = function (text1, text2) {
        this.dp = function (i, j) {
          // 递归结束条件，有一个字符串为空字符串
          if (i === -1 || j === -1) {
            return 0
          }
          // 相等即找到一个LCS的字符，加1后继续向前查找
          if (text1[i] === text2[j]) {
            return this.dp(i - 1, j - 1) + 1
          } else {
            // 没有找到LCS字符，则判断是移动哪个指针能使LCS更长
            return Math.max(
              this.dp(i - 1, j), // text1[i]不在LCS中，text2[j]在LCS中
              this.dp(i, j - 1), // text2[j]不在LCS中，text1[i]在LCS中
              this.dp(i - 1, j - 1) // text1[i]和text[2]都不在LCS中
            )
          }
        }
        // 两个指针i和j，分别指向字符串的最后一位，从后往前遍历
        return this.dp(text1.length - 1, text2.length - 1)
      }
      console.log(longestCommonSubsequence('abcde', 'ace'))
    </script>
  </body>
</html>
